#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // TreeNode* unflod(TreeNode* root)
    // {
    //     // cout << root->val << endl;
    //     if(root->left == nullptr && root->right == nullptr) return root;
    //     else if(root->left == nullptr) root->right = unflod(root->right);
    //     else if(root->right == nullptr)
    //     {
    //         root->right = unflod(root->left);
    //         root->left = nullptr;
    //     }
    //     else
    //     {
    //         TreeNode* tmp = root->right;
    //         root->right = unflod(root->left);
    //         root->left = nullptr;
    //         TreeNode* cur = root;
    //         while(cur && cur->right)
    //         {
    //             cur = cur->right;
    //         }
    //         cur->right = unflod(tmp);
    //     }
    //     return root;
    // }
    void flatten(TreeNode* root) {
        // if(root == nullptr) return;
        // unflod(root);

        for (TreeNode* cur = root; cur; cur = cur->right)
        {
            TreeNode* next = cur->left;
            for (; next && next->right; next = next->right);
            if (next)
            {
                next->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
        }
    }
};